package com.zp.self.module.level_4_算法练习.数据结构.String;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_49_字母异位词分组 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_49_字母异位词分组().groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
        System.out.println(new 力扣_49_字母异位词分组().groupAnagrams(new String[]{""}));
        System.out.println(new 力扣_49_字母异位词分组().groupAnagrams(new String[]{"a"}));
        System.out.println(new 力扣_49_字母异位词分组().groupAnagrams(new String[]{"bdddddddddd","bbbbbbbbbbc"}));
    }

    /**
    题目：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
     字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

     示例 1:
     输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
     输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

     示例 2:
     输入: strs = [""]
     输出: [[""]]

     示例 3:
     输入: strs = ["a"]
     输出: [["a"]]

    分析：
       1. 遍历每个字符串，生成26位图， 对比之前已经生成的.
        如果没有相同的，独立一个key. 如果有相同的则加入他们的List

       大神解法:利用质数来表示每一个字符的值，字符相乘
       大神解法:直接排序啊，我傻了啊......wow
    边界值 & 注意点：
       1.
     **/
    //利用位图来解答 ：击败5%
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String ,List<String>> map= new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String str = String.copyValueOf(chars);
            if(!map.containsKey(str))
                map.put(str,new ArrayList<>());
            map.get(str).add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }

    //1. 遍历每个字符串，生成26位图， 对比之前已经生成的. --- 菜了 【直接用String.hashcode  快余 String.equel 】
    public List<List<String>> groupAnagrams0(String[] strs) {
        Map<String ,List<String>> map= new HashMap<>();
        String  slipt ="-";
        for (int i = 0; i < strs.length; i++) {
            int[] weitu = new int[26];
            String str = strs[i];
            for (int j = 0; j < str.length(); j++)
                weitu[str.charAt(j)-'a']++;
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 26; j++)
                sb.append(weitu[j]).append(slipt);

            str = sb.toString();
            if(map.containsKey(str)){
                map.get(str).add(strs[i]);
            }else {
                List<String> list =new ArrayList<>();
                list.add(strs[i]);
                map.put(str,list);
            }
        }
        return new ArrayList<>(map.values());
    }

}
